package jm.algorithm.sort;

/**
 * @Description 计数排序实现
 * @date 2022/5/8 15:05
 */
public class CountingSort extends Sort<Integer> {

    @Override
    protected void sort() {
        // 获取数组最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }

        // 开辟内存空间
        int[] counts = new int[max + 1];

        // 统计次数
        for (int i = 0; i < arr.length; i++) {
            counts[arr[i]]++;
        }

        // 根据出现的次数对整数进行排序
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i] > 0) {
                arr[index] = i;
                index++;
                counts[i]--;
            }
        }
    }

}
